/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    // 哈希法
    /*
    RandomListNode* Clone(RandomListNode* pHead) {
        unordered_map<RandomListNode*, RandomListNode*> ump;
        RandomListNode* dummy = new RandomListNode(-1);
        RandomListNode* prev = dummy;
        RandomListNode* cur = pHead;
        while(cur) {
            RandomListNode* clone = new RandomListNode(cur->label);
            ump[cur]=clone;  // ****
            prev -> next = clone;
            cur = cur ->next;
            prev = prev->next;
        }
        cur = dummy->next;
        for(auto& [k,v]:ump) {
            v->random = k->random == nullptr ? nullptr : ump[k->random];
        }
        return dummy->next;
    }
    */
    // 链表拼接、拆分,三次遍历，空间复杂度O(1)
    RandomListNode* Clone(RandomListNode* p) {
        if(!p) return nullptr;
        RandomListNode* cur = p;
        while(cur) {
            RandomListNode* clone = new RandomListNode(cur->label);
            clone->next = cur->next;
            cur->next = clone;
            cur = clone ->next;
        }
        RandomListNode* old = p, *clone = p->next, *ret = p ->next;
        while(old) {
            clone->random =old->random ==nullptr? nullptr: old->random->next;
            if(old->next) old=old->next->next;
            if(clone->next) clone=clone->next->next;
        }
        old = p, clone = p->next;
        while(old) {
            if(old->next) old->next = old->next->next;
            if(clone->next) clone->next=clone->next->next;
            old=old->next;
            clone=clone->next;
        }
        return ret;
    }
};